package impl.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 05/10/2011
 * Time: 13:37:07
 * To change this template use File | Settings | File Templates.
 */
public class QuickThreeWaySorter extends AbstractSorter {
    public QuickThreeWaySorter() {
        super(SorterType.QUICK_THREE_PARTITION);
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        sort(c, list, 0, list.size()-1);
    }
    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        if(l<r){
            int pivot = r;
            int i = l;
            int p = l;
            int j = pivot-1;
            int q = pivot-1;
            while(i!=j){
                while((!greater(c, list, i, pivot))&&(i<j)){
                    if(equals(c, list, i, pivot)){
                        if(i!=p){
                            swap(list, i, p);
                        }
                        p++;
                    }
                    i++;
                }
                while(((greater(c, list, j, pivot))||(equals(c, list, j, pivot)))&&(j>i)){
                    if(equals(c, list, j, pivot)){
                        if(j!=q){
                            swap(list, j, q);
                        }
                        q--;
                    }
                    j--;
                }
                if(i!=j){
                    swap(list, i, j);
                }
            }
            if(greater(c, list, i, pivot) && i<pivot){
                swap(list, pivot, i);
                pivot = i;
            }
            int izq = 0;
            int der = 0;
            while(p>l){
                swap(list, p-1, pivot-p+l);
                p--;
                izq++;
            }
            while(q<r-1){
                swap(list, q+1, pivot+r-1-q);
                q++;
                der++;
            }
            sort(c, list, l, pivot-izq-1);
            sort(c, list, pivot+der+1, r);
        }
    }
}